{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Prime In Diagonal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #matrix #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #矩阵 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: diagonalPrime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #对角线上的质数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的二维整数数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>返回位于 <code>nums</code> 至少一条 <strong>对角线</strong> 上的最大 <strong>质数</strong> 。如果任一对角线上均不存在质数，返回<em> 0 。</em></p>\n",
    "\n",
    "<p>注意：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果某个整数大于 <code>1</code> ，且不存在除 <code>1</code> 和自身之外的正整数因子，则认为该整数是一个质数。</li>\n",
    "\t<li>如果存在整数 <code>i</code> ，使得&nbsp;<code>nums[i][i] = val</code> 或者&nbsp;<code>nums[i][nums.length - i - 1]= val</code> ，则认为整数 <code>val</code> 位于 <code>nums</code> 的一条对角线上。</li>\n",
    "</ul>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/03/06/screenshot-2023-03-06-at-45648-pm.png\" style=\"width: 181px; height: 121px;\" /></p>\n",
    "\n",
    "<p>在上图中，一条对角线是 <strong>[1,5,9]</strong> ，而另一条对角线是<strong> [3,5,7]</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [[1,2,3],[5,6,7],[9,10,11]]\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>数字 1、3、6、9 和 11 是所有 \"位于至少一条对角线上\" 的数字。由于 11 是最大的质数，故返回 11 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [[1,2,3],[5,17,7],[9,11,10]]\n",
    "<strong>输出：</strong>17\n",
    "<strong>解释：</strong>数字 1、3、9、10 和 17 是所有满足\"位于至少一条对角线上\"的数字。由于 17 是最大的质数，故返回 17 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 300</code></li>\n",
    "\t<li><code>nums.length == nums<sub>i</sub>.length</code></li>\n",
    "\t<li><code>1 &lt;= nums<span style=\"\">[i][j]</span>&nbsp;&lt;= 4*10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [prime-in-diagonal](https://leetcode.cn/problems/prime-in-diagonal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [prime-in-diagonal](https://leetcode.cn/problems/prime-in-diagonal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[5,6,7],[9,10,11]]', '[[1,2,3],[5,17,7],[9,11,10]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        def isprime(a:int)->bool:\n",
    "            b=int(sqrt(a))\n",
    "            for i in range(2,b+1):\n",
    "                if a%i==0:\n",
    "                    return False\n",
    "            return a>=2\n",
    "        res,n=0,len(nums)\n",
    "        for i,rows in enumerate(nums):\n",
    "            for x in rows[i],rows[-1-i]:\n",
    "                if x>res and isprime(x):\n",
    "                    res=x\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        def isprime(a:int)->bool:\n",
    "            b=int(sqrt(a))\n",
    "            for i in range(2,b+1):\n",
    "                if a%i==0:\n",
    "                    return False\n",
    "            return a>=2\n",
    "        res=0\n",
    "        for i,rows in enumerate(nums):\n",
    "            for x in rows[i],rows[-1-i]:\n",
    "                if x>res and isprime(x):\n",
    "                    res=x\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        m = len(nums)\n",
    "        ns = set()\n",
    "        for i in range(m):\n",
    "            ns.add(nums[i][i])\n",
    "            ns.add(nums[i][-1 - i])\n",
    "        ns = list(ns)\n",
    "        ns.sort(reverse = True)\n",
    "        for n in ns:\n",
    "            if n == 2 or n == 3:\n",
    "                return n\n",
    "            elif n > 1 and (n % 6 == 1 or n % 6 == 5):\n",
    "                na = True\n",
    "                for i in range(2, int(n ** 0.5) + 1):\n",
    "                    if n % i == 0:\n",
    "                        na = False\n",
    "                        break\n",
    "                if na:\n",
    "                    return n\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        def isprime(a:int)->bool:\n",
    "            if a<2:\n",
    "                return False\n",
    "            b=int(sqrt(a))\n",
    "            for i in range(2,b+1):\n",
    "                if a%i==0:\n",
    "                    return False\n",
    "            return True\n",
    "        res,n=0,len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i][i]>res and isprime(nums[i][i]):\n",
    "                res=nums[i][i]\n",
    "            if nums[i][n-i-1]>res and isprime(nums[i][n-i-1]):\n",
    "                res=nums[i][n-i-1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        s=[]\n",
    "        s1=[]\n",
    "        ss=[0]\n",
    "        for i in range(len(nums)):\n",
    "            s.append(nums[i][i])\n",
    "        for i in range(len(nums)):\n",
    "            s.append(nums[i][len(nums) - i - 1])\n",
    "        for i in s :\n",
    "            if i == 2 :\n",
    "                s1.append(2)\n",
    "            if i==1 or i%2==0 or i%3==0 or i%5==0 or i%7==0 or i%9==0 :\n",
    "                continue\n",
    "            else:\n",
    "                s1.append(i)\n",
    "        s1.sort(reverse=True)\n",
    "        for i in s1 :\n",
    "            aa=True\n",
    "            for a in range(2,i):\n",
    "                if i%a==0 :\n",
    "                    aa=False\n",
    "                    break\n",
    "            if aa :\n",
    "                ss.append(i)\n",
    "                break\n",
    "        return max(ss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]):\n",
    "        def judge_prime(n: int):\n",
    "            if n == 1:\n",
    "                return False\n",
    "            for i in range(2,int(n**0.5)+1):\n",
    "                if n % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        line = set([nums[i][i]  for i in range(len(nums))] + [nums[i][len(nums) - i - 1]  for i in range(len(nums))])\n",
    "        return sorted(list(filter(lambda x:judge_prime(x),line)))[-1] if len(list(filter(lambda x:judge_prime(x),line))) > 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "def isPrime(x):\n",
    "    if x == 1: return False\n",
    "    i = 2\n",
    "    while i*i <= x:\n",
    "        if x % i == 0:\n",
    "            return False\n",
    "        i += 1\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if isPrime(nums[i][i]):\n",
    "                res = max(res, nums[i][i])\n",
    "            if isPrime(nums[i][n-1-i]):\n",
    "                res =max(res, nums[i][n-1-i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "import numpy as np\n",
    "class Solution:\n",
    "\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        \n",
    "        def isPrime(n):\n",
    "            if n <= 1:\n",
    "                return False\n",
    "            for i in range(2, int(math.sqrt(n)) + 1):\n",
    "                if n % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        b = np.diag(nums)\n",
    "        b = list(b)\n",
    "        c=np.fliplr(nums)\n",
    "        cdiag=np.diag(c)\n",
    "        cc = list(cdiag)\n",
    "        returns = b+cc\n",
    "        ans = []\n",
    "        for i in returns:\n",
    "            if(isPrime(i)):\n",
    "                ans.append(i)\n",
    "        # print(max(ans))\n",
    "        if len(ans)==0:\n",
    "            return 0\n",
    "        ans_= max(ans)\n",
    "        return int(ans_) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def prime_sieve(n):\n",
    "    flag = n % 6 == 2\n",
    "    sieve = bytearray((n // 3 + flag >> 3) + 1)\n",
    "    for i in range(1, int(n**0.5) // 3 + 1):\n",
    "        if not (sieve[i >> 3] >> (i & 7)) & 1:\n",
    "            k = (3 * i + 1) | 1\n",
    "            for j in range(k * k // 3, n // 3 + flag, 2 * k):\n",
    "                sieve[j >> 3] |= 1 << (j & 7)\n",
    "            for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):\n",
    "                sieve[j >> 3] |= 1 << (j & 7)\n",
    "    return sieve\n",
    "\n",
    "\n",
    "def prime_list(n):\n",
    "    res = []\n",
    "    if n > 1:\n",
    "        res.append(2)\n",
    "    if n > 2:\n",
    "        res.append(3)\n",
    "    if n > 4:\n",
    "        sieve = prime_sieve(n + 1)\n",
    "        res.extend(3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not (sieve[i >> 3] >> (i & 7)) & 1)\n",
    "    return res\n",
    "\n",
    "P = set(prime_list(4 * 10 ** 6))\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, a: List[List[int]]) -> int:\n",
    "        n = len(a)\n",
    "        return max(max((a[i][i] for i in range(n) if a[i][i] in P), default=0), max((a[i][n-i-1] for i in range(n) if a[i][n-i-1] in P), default=0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        r = []\n",
    "        for i in range(len(nums)):\n",
    "            r.append(nums[i][i])\n",
    "            r.append(nums[i][len(nums) - 1 - i])\n",
    "        rec = {}\n",
    "        for i in range(2, max(r) + 1):\n",
    "            nn = int(i ** 0.5) + 1\n",
    "            s = 1\n",
    "            for n in rec.keys():\n",
    "                if i % n == 0:\n",
    "                    s = 0\n",
    "                    break\n",
    "                if n > nn:\n",
    "                    break\n",
    "            if s:\n",
    "                rec[i] = 1\n",
    "        res = 0\n",
    "        for v in r:\n",
    "            if rec.get(v):\n",
    "                res = max(res, v)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx = 4 * 10 ** 6\n",
    "is_prime = [True] * mx\n",
    "is_prime[1] = False\n",
    "for i in range(2, mx):\n",
    "    for j in range(i * i, mx, i):\n",
    "        is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            x = nums[i][i]\n",
    "            y = nums[i][n - i - 1]\n",
    "            if is_prime[x]:\n",
    "                ans = max(ans, x)\n",
    "            if is_prime[y]:\n",
    "                ans = max(ans, y)\n",
    "        return ans if is_prime[ans] else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "def euler(n: int) -> List[int]:\n",
    "    \"\"\"[2, x] 内的质数\"\"\"\n",
    "    primes = []\n",
    "    isPrime = [True] * (n + 1)\n",
    "    for i in range(2, n + 1):\n",
    "        if isPrime[i]:\n",
    "            primes.append(i)\n",
    "        for p in primes:\n",
    "            if i * p >= n:\n",
    "                break\n",
    "            isPrime[i * p] = False\n",
    "            if i % p == 0:  # p 是 lpf[i]\n",
    "                break\n",
    "    return primes\n",
    "\n",
    "primes = set(euler(4000010))\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i, row in enumerate(nums):\n",
    "            for x in row[i], row[-1 - i]:\n",
    "                if x > ans and x in primes:\n",
    "                    ans = x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "# import numpy as np\n",
    "\n",
    "# Python Version\n",
    "def get_primes(n):  #线性筛，把给定的n的质数筛选出来\n",
    "    pri = []\n",
    "    vis = [0] * (n + 1)\n",
    "\n",
    "    for i in range(2, n + 1):\n",
    "        if vis[i] == 0:\n",
    "            pri.append(i)\n",
    "        for j in range(len(pri)):\n",
    "            x = i * pri[j]\n",
    "            if x > n: break\n",
    "            vis[x] = 1\n",
    "            if i % pri[j] == 0:\n",
    "                break\n",
    "    return pri\n",
    "\n",
    "pri = set(get_primes(4000001))\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        arr = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            arr.append(nums[i][i])\n",
    "            arr.append(nums[i][n-i-1])\n",
    "        arr.sort()\n",
    "        for i in arr[::-1]:\n",
    "            if i in pri:\n",
    "                return i\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 4*10**6+1\n",
    "isprime = [0]*MX\n",
    "isprime[1]=1\n",
    "for i in range(2,MX):\n",
    "    if isprime[i]==0:\n",
    "        for j in range(i*i,MX,i):\n",
    "            isprime[j]=1\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "\n",
    "        n  = len(nums)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            t1 = nums[i][i]\n",
    "            t2 = nums[i][n-i-1]\n",
    "            if isprime[t1]==0 and t1 >ans:\n",
    "                ans =t1\n",
    "            if isprime[t2]==0 and t2 >ans:\n",
    "                ans =t2\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "m = 4 * 10 ** 6 + 2\n",
    "pi = [True for i in range(m)]\n",
    "pi[1] = False\n",
    "for i in range(2, m):\n",
    "    if pi[i]:\n",
    "        j = i\n",
    "        while j * i < m:\n",
    "            pi[i * j] = False\n",
    "            j += 1\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        m, n = len(nums), len(nums[0])\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            if pi[nums[i][i]]:\n",
    "                res = max(res, nums[i][i])\n",
    "            i += 1\n",
    "        i = m - 1\n",
    "        j = 0\n",
    "        while i >= 0:\n",
    "            if pi[nums[i][j]]:\n",
    "                res = max(res, nums[i][j])\n",
    "            i -= 1\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 1300 ms ... 8 % ... 57.6 MB ... 12 %\n",
    "        #  time: O(r)\n",
    "        # space: O(r)\n",
    "        \n",
    "        n = len(nums)\n",
    "        mx = max(max(row) for row in nums)\n",
    "        isprime = [True] * (mx + 1)\n",
    "        for i in range(2, mx + 1):\n",
    "            if isprime[i]:\n",
    "                v = i * i\n",
    "                while v <= mx:\n",
    "                    isprime[v] = False\n",
    "                    v += i\n",
    "        diag = set()\n",
    "        for i in range(n):\n",
    "            diag.add(nums[i][i])\n",
    "            diag.add(nums[i][n-1-i])\n",
    "        for v in range(mx, 1, -1):\n",
    "            if isprime[v] and v in diag:\n",
    "                return v\n",
    "        return 0\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 4 * (10 ** 6) + 1\n",
    "is_prime = [True] * MX\n",
    "is_prime[1] = False\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i][i] > ans and is_prime[nums[i][i]]:\n",
    "                ans = nums[i][i]\n",
    "            if nums[i][-1-i] > ans and is_prime[nums[i][-1-i]]:\n",
    "                ans = nums[i][-1-i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diagonalPrime(self, nums: List[List[int]]) -> int:\n",
    "        end = 0\n",
    "        for r in nums:\n",
    "            end = max(end, max(r))\n",
    "        end += 1\n",
    "        is_primer = [True] * end\n",
    "        is_primer[0] = is_primer[1] = False\n",
    "        for i in range(2, end):\n",
    "            if not is_primer[i]: continue\n",
    "            for j in range(i*i, end, i):\n",
    "                is_primer[j] = False\n",
    "        \n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "                if is_primer[nums[i][i]]:\n",
    "                    ans = max(ans, nums[i][i])\n",
    "                if is_primer[nums[i][n-i-1]]:\n",
    "                    ans = max(ans, nums[i][n-i-1])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
